Deadlock detection
分散システム$ S = {P_1, P_2, ..., P_n}があるとする。$ P_i: プロセス
ここで、$ \Pi = {P_1, P_2, ..., P_n}
有向枝$ (P, Q) \in Eはプロセス$ Pがプロセス$ Qを待っていることを示す
例: https://scrapbox.io/files/66106ed70179f60024b38eaf.png
$ D(P)={Q},\ D(Q) = {R},\ D(R) = {P},\ D(S) = {R}
要は有向閉路があったらオシマイkekeho.icon
Deadlock detectionにおいては、有向閉路の存在があるかどうかチェックすればOK
Deadlock detection algorithm 1
仮定
1. 分散システム$ Sはある別のシステム$ S^*上で稼働していると仮定。そのうえで、$ P_i \in \Piを管理する、システム$ S^*上のプロセス$ P^*_iは$ D(P_i)を把握しているとする
2. $ P^*_i \in S^*は、$ P_j \in S^* \ (j \neq i)とメッセージ交換が可能
3. プロセスも通信リンクも故障しないことを仮定
4. 各プロセスの持つ入力情報が変化しないStatic problemとして捉える。少なくともアルゴリズム実行中に、$ D(P_i)が変化しないことを仮定 initiator $ P^*_1: Deadlock detection algorithmを開始したいプロセス 擬似コード
$ P^*_iがinitiatorの場合:
1. for all $ j = 2, 3, ..., n do Send($ P^*_j, Request)
2. for all $ j = 2, 3, ..., n do Receive($ P^*_j, $ D_j)
4. $ Gに対し、有向閉路発見アルゴリズムを適用
$ P^*_iがinitiatorではない場合:
1. Receive($ P^*_1, M);
2. if M = Request then Send($ P^*_1, $ D(P_i))
定理
1. このアルゴリズムの始動時にシステムがデッドロック状態にあるならば、それを検知する
非同期システムにおいては、デッドロックがある=>検知されるは真でも、その逆は成り立たない(検知されたからといって、本当にデッドロックが起きているとは限らない)
各プロセス$ P^*_iがレスポンスを返すタイミングはバラバラなので、バラバラな時間における依存関係が重ね合わさってしまう